-------<br />METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)<br />-------<br />Workshop on Metric embeddings, algorithms and hardness of approximation<br />January 17-21, 2011<br />-------<br />Jan 19, 14:00-15:00<br />Prahladh Harsha (TIFR Mumbai)<br />Composition of low-error 2-query PCPs using decodable PCPs<br />-------<br />Proof composition is an essential ingredient in all constructions of<br />probabilistically checkable proofs (PCPs). In this talk, I'll present<br />a generic, composition method for low error two-query PCPs. This<br />extends earlier composition methods (such as the ones used in Dinur's<br />combinatorial construction of PCPs) which were either inapplicable in<br />the low-error regime or non-modular (i.e., very much tailored to the<br />specific PCPs that were being composed), if not both. Also,<br />composition in the low error regime suffered from incurring an extra<br />consistency query, resulting in PCPs that are not two-query and hence,<br />much less useful for hardness-of-approximation reductions.<br /><br />I'll then illustrate how this composition theorem can be used to give<br />a simple and modular construction of low-error 2-query PCPs of nearly<br />linear length [Moshkovitz and Raz, 2008]. One of the critical<br />components in the composition is a variant of PCP called "decodable<br />PCP". A decodable PCP, besides being locally checkable as a standard<br />PCP, is also locally decodable, in the sense, that the original NP<br />witness can be locally decoded from it.<br /><br />Joint work with Irit Dinur.
